package leetcode_1601_1700;

import java.util.Arrays;

public class LeeCode_1626_2 {
    public static void main(String[] args) {
        System.out.println(bestTeamScore(new int[]{1, 3, 5, 10, 15}, new int[]{1, 2, 3, 4, 5}));
        System.out.println(bestTeamScore(new int[]{4,5,6,5}, new int[]{2,1,2,1}));
        System.out.println(bestTeamScore(new int[]{1,2,3,5}, new int[]{8,9,10,1}));
        System.out.println(bestTeamScore(new int[]{1,1,1,1,1,1,1,1,1,1},
                new int[]{811,364,124,873,790,656,581,446,885,134}));
    }

    private static int bestTeamScore(int[] scores, int[] ages) {
        int n = scores.length;
        int[][] people = new int[n][2];
        for (int i = 0; i < n; i++) {
            people[i] = new int[]{scores[i], ages[i]};
        }
        Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        int[] dp = new int[n];
        int res = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                if (people[j][1] <= people[i][1]){
                    dp[i] = Math.max(dp[j], dp[i]);
                }
            }
            dp[i] += people[i][0];
            res = Math.max(dp[i], res);
        }
        return res;
    }
}
